package sy6_Behavioral_Pattern.interpreter.other;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

/*
 *  功能：做若干整数的加、减、乘、除和幂运算，如 1+2*3-32/2^3
 */

class Context{  //角色1：环境类Context
	
	private AbstractExpression syntaxTree;  //表达式语法树

	public AbstractExpression getSyntaxTree() {  //getter
		return syntaxTree;
	}

	public Context(String expStr) throws Exception{  //有参构造方式；构建AST
		//【词法分析】分离出数据和运算符；+、*和^是Java正则处理的特殊字符，因此，需要使用转义符。
		String[] nums = expStr.split("\\+|-|\\*|/|\\^"); //必须使用或运算符|，而不能是||
		System.out.println("测试参加运算的整数："+Arrays.toString(nums));
		Queue<String> opQueue = new LinkedList<String>();  //创建存取运算符队列
		for(int i=0;i<expStr.length();i++) {  //从运算表达式里取运算符
			String temp=expStr.substring(i,i+1);  //取一个字符
			if(temp.equals("+")||temp.equals("-")||temp.equals("*")||temp.equals("/")||temp.equals("^")){
				opQueue.add(temp);  //加到队列opQueue
			}
		}
		System.out.println("测试参加运算的运算符队列："+opQueue);  //先进先出

		List<String> ASTElementList = new ArrayList<String>();   //创建抽象语法树元素列表
		for(String string : nums) {
			ASTElementList.add(string);
			if(!opQueue.isEmpty()) {
				ASTElementList.add(opQueue.poll());  //从列取出、添加至列表
			}
		}
		System.out.println("测试抽象语法树元素列表："+ASTElementList);
		Stack<AbstractExpression> numStack = new Stack<>(); //创建抽象操作数栈
		Stack<String> opStack  = new Stack<>();  //创建操作符栈 
		//初始栈顶为null(级别为0)，是为了遍历过程能正常结束（结束标志）。
		opStack.push(null);  //null对应的运算优先级为0；+-优先级为1；*/优先级为2；^的优先级为3
		for(String str:ASTElementList) {  //形成语法树AST，优先级高的位于叶子
			if("+".equals(str)||"-".equals(str)||"*".equals(str)||"/".equals(str)||"^".equals(str)) {
				 //遇到运算符时，需要与opStack栈顶元素比较。
				 while(getPriority(str)<=getPriority(opStack.peek())){ //peek()是获取栈顶元素
					 //当顶元素的优先级>=运算符的优先级时，弹栈并计算。其中=表示同级运算符先出现先运算
					 AbstractExpression right = numStack.pop();
					 AbstractExpression left = numStack.pop();
					 String op=opStack.pop();  //出栈操作改变栈顶元素（优先级）
                     numStack.push(abstractCalculate(left,right,op));  //将运算结果入数据栈
                 }
				 //运算符总是要入栈的，在此之前，已经解决了优先级与同级。
                 opStack.push(str);  //操作符入栈，在此之前，opStack除了null外，最多可以包含2个运算符。
			}else {  
				//遇到操作数时，创建终结表达式并压入numStack栈
				numStack.push(new TerminalExpression(str));
            }
		}
		//遍历结束后，符号栈只有2个元素，其中位于栈底的null用于结束解释。
		while(opStack.peek()!=null) {  
			AbstractExpression right=numStack.pop();
			AbstractExpression left=numStack.pop();
	        numStack.push(abstractCalculate(left,right,opStack.pop()));  //递归计算
	    }
		syntaxTree=numStack.pop();  //通过Debug调试，可以查看其嵌套结构（就是一个AST）。
	}
	
	private int getPriority(String s){  //获取优先级
        if(s==null) {  //特殊元素，对应于opStack初始栈顶为null（级别为0）
        	return 0;  //设定优先级
        }
		switch(s){
			case "+":;
			case "-":
				return 1;    //设定优先级
			case "*":;
			case "/":
				return 2;  //设定优先级
			case "^":
				return 3;  //设定优先级
			default:
				return 0;
		}
	}
	
	private AbstractExpression abstractCalculate(AbstractExpression left, AbstractExpression right, String op) throws Exception {
        switch(op){
	        case "+":
	            return new AddNonterminalExpression(left, right);  //加法
	        case "-":
	            return new SubNonterminalExpression(left, right);  //减法
	        case "*":
	            return new MulNonterminalExpression(left, right);  //乘法
	        case "/":
	            return new DivNonterminalExpression(left, right);  //除法
	        case "^":
	            return new PowerNonterminalExpression(left, right);  //幂运算	            
	        default:
	        	throw new Exception("illegal operator!");
        }
    }
}

abstract class AbstractExpression{ //角色2：抽象表达式AbstractExpression
	public abstract int interpret();  //解释
}

class TerminalExpression extends AbstractExpression{   //终结符表达式TerminalExpression
	
	private String num;  //单个变量表达式
	
	public TerminalExpression(String num) {  //构造器
		this.num = num;
	}

	@Override
	public int interpret() {  //实现抽象方法
		return Integer.parseInt(num);  //返回变量名的值
	}
}

abstract class NonterminalExpression extends AbstractExpression{  //角色4：非终结符表达式NonterminalExpression
	
	protected AbstractExpression left;
	protected AbstractExpression right;
	
	public NonterminalExpression(AbstractExpression left, AbstractExpression right) { //构造方法
		this.left = left;
		this.right = right;
	}
	//抽象类NonterminalExpression继承抽象类AbstractExpression，不必重写父类的抽象方法
}

class AddNonterminalExpression extends NonterminalExpression{  //加法解析器
	public AddNonterminalExpression(AbstractExpression left, AbstractExpression right) {  //构造器
		super(left, right);  //调用父类构造方法
	}
	
	@Override
	public int interpret() {  //加法实现
		int leftValue=super.left.interpret();
		int rightValue=super.right.interpret();
		System.out.println("加法计算："+leftValue+"+"+rightValue+"="+(leftValue+rightValue));//测试
		return leftValue+rightValue;  //方法interpret()递归调用
	}
}

class SubNonterminalExpression extends NonterminalExpression{  //减法实现
	public SubNonterminalExpression(AbstractExpression left, AbstractExpression right) {  //构造器
		super(left, right);
	}
	
	@Override
	public int interpret() {
		int leftValue=super.left.interpret();
		int rightValue=super.right.interpret();
		System.out.println("减法法计算："+leftValue+"-"+rightValue+"="+(leftValue-rightValue));//测试
		return leftValue-rightValue;  //方法interpret()递归调用
	}
}

class MulNonterminalExpression extends NonterminalExpression{  //乘法实现
	public MulNonterminalExpression(AbstractExpression left, AbstractExpression right) {  //构造器
		super(left, right);
	}
	
	@Override
	public int interpret() {
		int leftValue=super.left.interpret();
		int rightValue=super.right.interpret();
		System.out.println("乘法计算："+leftValue+"*"+rightValue+"="+(leftValue*rightValue));//测试
		return leftValue*rightValue;  //方法interpret()递归调用
	}
}

class DivNonterminalExpression extends NonterminalExpression{  //除法实现
	public DivNonterminalExpression(AbstractExpression left, AbstractExpression right) {  //构造器
		super(left, right);
	}
	
	@Override
	public int interpret() {
		int leftValue=super.left.interpret();
		int rightValue=super.right.interpret();
		System.out.println("除法计算："+leftValue+"/"+rightValue+"="+(leftValue/rightValue));//测试
		return leftValue/rightValue;  //方法interpret()递归调用
	}
}

class PowerNonterminalExpression extends NonterminalExpression{  //幂运算实现
	public PowerNonterminalExpression(AbstractExpression left, AbstractExpression right) {  //构造器
		super(left, right);
	}
	
	@Override
	public int interpret() {
		int leftValue=super.left.interpret();
		int rightValue=super.right.interpret();
		System.out.println("幂计算："+leftValue+"^"+rightValue+"="+(int)Math.pow(leftValue,rightValue));//测试
		return (int)Math.pow(leftValue,rightValue);  //方法interpret()递归调用
	}
}

public class Client {  //客户端
	public static void main(String[] args) throws NumberFormatException, Exception {
		System.out.print("请输入要计算的四则运算表达式：");
		String expStr=(new BufferedReader(new InputStreamReader(System.in))).readLine(); 
		Context context = new Context(expStr);  //创建上下文对象
		AbstractExpression syntaxTree=context.getSyntaxTree();  //获取抽象语法树AST
		System.out.println("运算结果："+expStr+"="+syntaxTree.interpret());  //计算并输出
	}
}